package indi.caspar.algorithms.sort;

/**
 * 归并排序——自顶向下
 * Created by casparhuan on 2017/6/21.
 */
public class MergeSorts {

    private static Comparable[] aux;
    public static void sort(Comparable[] a,int low,int hi){
        if (low >=hi)   return;
        int mid = low + (hi-low)/2 ;
        sort(a,low , mid );
        sort(a,mid+1, hi );
        merge(a,low,mid,hi);
    }

    public static void sort(Comparable[] a){
        aux = new String[a.length];
        sort(a,0,a.length-1);
    }

    public static void merge(Comparable[] a, int low ,int mid ,int hi){
        for (int i = low; i <= hi ; i++) {
            aux[i] = a[i];
        }
        int i=low,j=mid+1;

        for (int k = low; k <= hi; k++) {
            if (i>mid)  a[k] = aux[j++];
            else if (j>hi)  a[k] = aux[i++];
            else if ( SortsAlgUtil.less(aux[j],aux[i]))  a[k] = aux[j++];
            else  a[k] = aux[i++];
        }
    }

    public static void main(String[] args) {
        String[] b = {"S","O","R","T","E","X","A","M","P","L","E"};
        aux = new String[b.length];
        sort(b);
        System.out.println(SortsAlgUtil.isSorted(b));
        SortsAlgUtil.show(b);
    }
}
